package com.example.exercises;

/**
 * 第k大
 * 题目描述
 * 有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
 * 
 * 给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
 * 
 * 示例1
 * 输入
 * 复制
 * [1,3,5,2,2],5,3
 * 返回值 2
 *
 * 注意这是返回第k大的数，与之前第k小相反，可以用数组末尾n减去k值，转而去求第x小的数
 * x=n-k+1
 * x小==k大
 */
public class SmallestKNumber2 {
    private static void quickSort(int[] n, int left, int right, int k, int n2) {
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int key = n[left];
        //一次while循环完成一轮快速排序，最终确定切割点key的位置
        while (i < j) {
            while (i < j && n[j] >= key) {
                j--;
            }
            while (i < j && n[i] <= key) {
                i++;
            }
            //将n[i]>key,n[j]<key的进行替换
            if (i < j) {
                int temp = n[i];
                n[i] = n[j];
                n[j] = temp;
            }
        }
        //将n[i]赋给起始点，将key的值赋给它的最终位置i点
        n[left] = n[i];
        n[i] = key;
        //分别对切割点左右两个数组进行递归
        /**
         * 注意，真正的快排没有底下的if判断，而是两个递归都执行，
         * 但此题可根据此技巧减少大量的多余操作，节省时间
         * */
        if (i > n2 - k) {
            quickSort(n, left, i - 1, k, n2);
        } else {
            quickSort(n, i + 1, right, k, n2);
        }
    }

    public int findKth(int[] a, int n, int K) {
        int left = 0;
        int right = a.length - 1;
        quickSort(a, left, right, K, n);
        // write code here
        //因为数组本身从0开始，所以返回的是n-k
        return a[n - K];
    }
}
